package com.asa.shishu;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class BaseMath {

	
	

	/**
	 * 最大公约数
	 * @param a
	 * @param b
	 * @return
	 */
	public static int GCD(int a,int b) {
		
		if (a==0) {
			return b;
		}
		if (b==0) {
			return a;
		}
		
		
		
		int[] gcDtmp = GCDtmp(a, b);
		if (gcDtmp[1]==0) {
			return gcDtmp[0];
		}
		
		
		return 1;
		
	}

	
	/**
	 * 最大公约数
	 * 使用辗转相除法
	 * @param a	需要求最大公约数的两个数
	 * @param b 需要求最大公约数的两个数
	 * @return	数组，如果int[1]==1说明互素，如果int[1]==0，那么int[0]就是它们的最大公约数
	 */
	public static int[] GCDtmp(int a,int b) {
		a = Math.abs(a);
		b = Math.abs(b);
		int[] result = new int[2];
		if (a>b) {
			
			int asa = a/b;
			int asb = a%b;
//			System.out.println( asa + "    " + asb   );
			if (asb==0 ||asb==1) {//跳出递归条件
				result[0] = b;
				result[1] = asb;

				return result;
				
			}else {
				return GCDtmp(b, asb);
			}
			
			
		}else {
			int asa = b/a;
			int asb = b%a;
			
			if (asb==0 ||asb==1) {//跳出递归条件
				result[0] = a;
				result[1] = asb;

				return result;
				
			}else {
				return GCDtmp(a, asb);
			}
			
			
		}
		
	}
	
	

	/**
	 * 最小公倍数
	 * 根据定理：若a和b是两个正整数，则GCD(a,b)*LCM(a,b) = a*b
	 * @param a
	 * @param b
	 * @return
	 */
	public static int LCM(int a,int b) {
		
		int[] gcd = GCDtmp(a, b);
		
		if (gcd[1]==0) {
			
			return a*b / gcd[0];
			
		}
		return a*b;
	}

	
	/**
	 * 10进制转换成别的进制
	 * 感觉没必要自己实现
	 * 
	 */
	public static String jinzhi(int a,int N) {
		
		
		
		
		return null;
	}

	
	
	/**
	 * 判断一个数是否是素数
	 * @param args
	 */
	public static boolean issu(int num) {
		
		
		int i = 0;
		int isprime = 1;//标志位，默认是素数
	 
		for (i = 2; i < num/2 +1; i++)//好菜的算法，但我也想不出其他方法了
		{
			if (num%i == 0)
			{
				isprime = 0;
			}
		}
		return isprime == 1;//检查标志位的值
		
		
	}
	
	public static boolean issu2(int num) {
		double sqrt = Math.sqrt(num);
		int asa = (int) sqrt;
		
		List<Integer> asb = new ArrayList<Integer>();
		for (int i = 0; i < asa; i++) {
			
			boolean issu = issu(i);
			if (issu) {
				asb.add(i);
			}
			
		}
		
		
		for (int i = 0; i < asb.size(); i++) {
			Integer integer = asb.get(i);
			
			int asc = num%integer;
			if (asc==0) {
				return false;
			}
			
		}
		
		return true;//检查标志位的值
		
		
	}
	
	
	/**
	 * 把一个数分解为质数的乘积
	 * @param num
	 * @return
	 */
	public static List<Integer> primeCount(int num) {
		List<Integer> sb = new ArrayList();
		int minNumber = 2;// 定义最小的质数
		while (minNumber < num) {
			if (num % minNumber == 0) {
				num = num / minNumber;
//				sb.append(minNumber + "*");
				sb.add(minNumber);
			} else {
				minNumber++;
			}
		}
		sb.add(minNumber);
//		System.out.print(sb.toString());
		return sb;
	}

	
	
	
	
	public static void main(String[] args) {
		
//		
//		int[] gcd = GCDtmp(15, 45);
//		for (int i = 0; i < gcd.length; i++) {
//			System.out.println(gcd[i]);
//		}
		
		
//		System.out.println(LCM(540, 504));
		
		
		boolean issu = issu(2017);
		System.out.println(issu);
		
		System.out.println(Math.sqrt(2017));
		
		
		
	}
	
	
	
	
	
	
	
	
}
